#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define y1 y_alpha_1

using namespace std;

using ll = long long;
using db = double;
using vec = vector<int>;
using pii = pair<int,int>;

int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-',ch = getchar();
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
	return f ? -x : x;
}

const int N = 110;
const int M = 1010;
const int inf = 1e9 + 5;
const ll INF = 1e18;

int n,m,K,B[N][M],S[N][M],d[N][N],cost[N][N];
ll w[N][N];

bool check(ll x) {
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++) {
			w[i][j] = i == j ? -INF : (cost[i][j] - d[i][j] * x);
		}
	for(int k = 1;k <= n;k++)
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				w[i][j] = max(w[i][j],w[i][k] + w[k][j]);
	for(int i = 1;i <= n;i++) if(w[i][i] >= 0) return 1;
	return 0;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in,K = in;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= K;j++) {
			B[i][j] = in,B[i][j] = B[i][j] == - 1 ? inf : B[i][j];
			S[i][j] = in,S[i][j] = S[i][j] == - 1 ? 0 : S[i][j];
		}
	for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) d[i][j] = inf; for(int i = 1,u,v;i <= m;i++) u = in,v = in,d[u][v] = in;
	for(int k = 1;k <= n;k++)
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++) 
			for(int k = 1;k <= K;k++) cost[i][j] = max(cost[i][j],S[j][k] - B[i][k]);
	int l = 0,r = 1e9;
	while(l <= r) {
		ll mid = l + r >> 1;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	printf("%d\n",l - 1);
	return 0;
}
